package LeetCode刷题;

import java.util.ArrayList;
import java.util.List;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-10 19:21
 * @description: Functions of this class is
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 有效括号组合需满足：左括号必须以正确的顺序闭合。
 *
 * 官方做法：
 * （回溯递归法）
 * class Solution {
 *     public List<String> generateParenthesis(int n) {
 *         List<String> ans = new ArrayList<String>();
 *         backtrack(ans, new StringBuilder(), 0, 0, n);
 *         return ans;
 *     }
 *
 *     public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
 *         if (cur.length() == max * 2) {
 *             ans.add(cur.toString());
 *             return;
 *         }
 *         if (open < max) {
 *             cur.append('(');
 *             backtrack(ans, cur, open + 1, close, max);
 *             cur.deleteCharAt(cur.length() - 1);//!!!!!!!!!!!!!不要忘记在这里删除！！！！！！！！！！！！！！！
 *         }
 *         if (close < open) {
 *             cur.append(')');
 *             backtrack(ans, cur, open, close + 1, max);
 *             cur.deleteCharAt(cur.length() - 1);//!!!!!!!!!!!!!不要忘记在这里删除！！！！！！！！！！！！！！！
 *         }
 *     }
 * }
 **/
public class NoNo括号生成 {
    public static void main(String args[]){
        System.out.println(generateParenthesis(3));
    }
    public static List<String> generateParenthesis(int n) {
        //用递归做
        List<String>ans=new ArrayList<>();
        dfs(n,ans,new StringBuffer(n<<1),0,0);
        return ans;
    }
    private static void dfs(int n,List<String>ans,StringBuffer sub,int leftNum,int rightNum){
        if(sub.length()==n<<1){//说明总长度到达了要求
            ans.add(sub.toString());//就添加一个方案到集合中
            return;
        }
        //否则长度还没有到达要求
        //开始比较左括号与右括号数量
        if(leftNum<n){//如果左括号的数量小于其应存在的数量
            sub.append('(');
            dfs(n,ans,sub,leftNum+1,rightNum);
            //当回退的时候，就删除之前添加进去的那个括号，即末尾的那个括号
            sub.deleteCharAt(sub.length()-1);
        }
        //来到这里说明左括号的数量已经到达了要求了
        //即开始判断右括号的数量
        /**
         * 如果左括号数量不大于 n，我们可以放一个左括号。
         * 如果右括号数量小于左括号的数量，我们可以放一个右括号。
         */
        if(rightNum<leftNum){//如果右括号的数量比左括号
            sub.append(')');
            dfs(n,ans,sub,leftNum,rightNum+1);
            //当回退的时候，就删除之前添加进去的那个括号，即末尾的那个括号
            sub.deleteCharAt(sub.length()-1);
        }

    }

}